Un arbre binaire de recherche est un arbre qui possède pour chacun de ses nœuds la propriété suivante sa clef est supérieure à toutes les clefs de ses descendants de gauche et plus petite ou égale à toutes les clefs de ses descendants de droite.
Un arbre binaire n'est pas un tas en effet dans ce dernier on sait juste que la clef d'un nœud est plus grande que celle de ses descendants.
L’intérêt premier d'un arbre de recherche se trouve dans son nom : faire des recherches. En général une recherche dans un arbre de recherche de taille n se fait en ln(n) (comme une recherche dichotomique dans un tableau) avec cependant une propriété supplémentaire l'insertion se fait aussi en O(ln(n)) (dans un tableau l'insertion se fait en O(n) car il faut décaler les éléments).